import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author kaho
 * @since 2021/3/11
 */
public class _面试题16_25_LRU缓存 {

//    class LRUCache {
//
//        public LRUCache(int capacity) {
//
//        }
//
//        public int get(int key) {
//
//        }
//
//        public void put(int key, int value) {
//
//        }
//    }

    class LRUCache1 {
        Map<Integer, ListNode> map;
        int capacity;
        ListNode head = new ListNode(-1,-1);
        ListNode tail = new ListNode(-1,-1);
        public LRUCache1(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>();
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            ListNode listNode = map.get(key);
            if (listNode == null) {
                return -1;
            }
            listNode.pre.next = listNode.next;
            listNode.next.pre = listNode.pre;
            removeToTail(listNode);
            return listNode.value;
        }

        private void removeToTail(ListNode listNode) {
            listNode.pre = tail.pre;
            tail.pre = listNode;
            listNode.pre.next = listNode;
            listNode.next = tail;
        }

        public void put(int key, int value) {
            if (get(key)!=-1) {
                map.get(key).value = value;
                return;
            }
            ListNode listNode = new ListNode(key, value);
            map.put(key, listNode);
            removeToTail(listNode);
            if (map.size()>capacity) {
                map.remove(head.next.key);
                head.next = head.next.next;
                head.next.pre = head;
            }
        }
    }

    class ListNode{
        int key;
        int value;
        ListNode pre;
        ListNode next;

        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
            this.pre = null;
            this.next = null;
        }
    }

    class LRUCache {
        int cap;
        Map<Integer, Integer> map;
        public LRUCache(int capacity) {
            cap = capacity;
            map = new LinkedHashMap<>((int)((float)cap*0.75f+1.0f), 0.75f, true);
        }

        public int get(int key) {
            Integer integer = map.get(key);
            if (integer == null) {
                return -1;
            }
            return integer;
        }

        public void put(int key, int value) {
            map.put(key, value);
            if (map.size()>cap) {
                map.remove(map.entrySet().iterator().next().getKey());
            }
        }
    }
}
